package com.fengdi.book.easy;

/**
 * @author FengDi
 * @Description 动态规划类问题
 * */
public class DynamicProgram {
    public static class ClimbStairs {
        public int climbStairs(int n) {
            if (n <= 1) return n;
            int count = 0;
            // dp[i]表示到第i级台阶有几种跳法
            int[] dp = new int[n + 1];
            dp[1]=1;
            dp[2]=2;
            for (int i = 3; i <= n; i++) {
                /*
                    由于dp[i]表示第i级台阶有多少种跳法，每次可以跳一级也可以跳两级，
                    因此到达第i级台阶时可以是从i-1跳上来的也可以是从i-2跳上来的
                    对于两种不同的跳法都会产生一条路径
                 */
                dp[i] = dp[i-1] + dp[i-2];
            }
            return dp[n];
        }
    }

    public static class MaxProfit {
        public int maxProfit(int[] prices) {
            if (prices == null || prices.length == 0) return 0;

            int[][] dp = new int[prices.length][2];
            dp[0][0] = 0;
            dp[0][1] = -prices[0];
            for (int i = 1; i < prices.length; i++) {
                dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
                dp[i][1] = Math.max(-prices[i], dp[i-1][1]);
            }
            return dp[prices.length-1][0];
        }
    }

    public static class MaxSubArray {
        public int maxSubArray(int[] nums) {
            if (nums == null || nums.length == 0) return 0;
            if (nums.length == 1) return nums[0];

            int[] dp = new int[nums.length];
            dp[0] = nums[0];
            int max = dp[0];
            for (int i = 1; i < nums.length; i++) {
                dp[i] = Math.max(dp[i - 1], 0) + nums[i];
                max = Math.max(max, dp[i]);
            }

            return max;
        }
    }

    public static class Rob {
        public int rob(int[] nums) {
            if (nums == null || nums.length == 0) return 0;
            if (nums.length == 1) return nums[0];

            // dp[i][1] 表示偷第i间房得到的钱，dp[i][0]表示不偷得到的钱
            int[][] dp = new int[nums.length][2];
            dp[0][0] = 0;
            dp[0][1] = nums[0];
            for (int i = 1; i < nums.length; i++) {
                dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]);
                dp[i][1] = dp[i-1][0] + nums[i];
            }

            return Math.max(dp[nums.length-1][0], dp[nums.length-1][1]);
        }
    }
}
